
#pragma once

#include <sstream>
#include <string>
#include <vector>
#include <ctype.h>
#include <algorithm>
#include "hr_time.h"
#include "SimpleLog.h"

using namespace std;

namespace quicks {
	
	struct matchchar {
		wchar_t c;
		bool matches;
	};
	typedef struct matchchar matchchar_t;
	typedef basic_string<matchchar_t, char_traits<matchchar_t>, allocator<matchchar_t> > matchstring;
	// string converter functions
	void MatchStringToWString(const matchstring& ms, wstring& ws);
	void WStringToMatchStringUnMatched(const wstring& ws, matchstring& ms);
	void WStringToString(const wstring& ws, string& s);

	template<class S> 
	struct MatchInput {
		const wstring* str;
		const S* data;
	};
	template<class U> 
	struct MatchOutput {
		matchstring str;
		int score;
		const U* data;
	};
	template<class U>
	bool operator < (const MatchOutput<U>& left, const MatchOutput<U>& right) { 
		return (left.score > right.score);
	}
	
	template<class T> 
	class IdoComplete {
	public:
		IdoComplete() {}
		~IdoComplete() {}
		typedef MatchOutput<T> Match;
		typedef vector<Match> MatchVector;
		struct MatchResult {
			wstring hint;
			MatchVector matches;
		};

		void MatchInput(MatchResult& result, const wstring& key, const vector<MatchInput<T>>& haystack) {

			result.matches.clear();
			result.hint.clear();
			if (key.size() > 0) {
				stringstream o1;
				string skey;
				WStringToString(key, skey);
				o1 << "matching \"" << skey << "\"" << "\n";
				LOG(o1.str());
				for (unsigned int i = 0; i < haystack.size(); i++) {
					MatchOutput<T> mo;
					mo.data = haystack[i].data;
					CStopWatch matchTime;
					matchTime.startTimer();
					mo.score = SimpleInnerMatch(mo.str, key, *(haystack[i].str), 0, 0, 0);
					matchTime.stopTimer();
/*					stringstream o;
					o << "simple match took " << matchTime.getElapsedTime() << "s" << "\n";
					LOG(o.str());*/
					//int quikScore = QuickInnerMatch(mo.str, key, *(haystack[i].str));
					if (mo.score > 0) {
						result.matches.push_back(mo);
					}
				}
				// use stable sort here so that the more recent ones stay more recent, depending on relevance
				stable_sort(result.matches.begin(), result.matches.end()); 

				//CStopWatch timeHint;
				//timeHint.startTimer();

				// find largest common substring after key[xxx]
				int nLeastLen = 0xffffff;
				bool bMatchedAll = true;
				bool bHintInitialized = false;
				for (unsigned int i = 0; i < result.matches.size() && bMatchedAll; i++) {
					bool bMatchedThis = false;
					unsigned int k = 0;
					// find the beginning of each match
					for (; k < result.matches[i].str.size(); k++) {
						// 1. match the original key
						unsigned int j = 0;
						for (; j < key.size(); j++) {
							if ( towlower(key[j]) != towlower(result.matches[i].str[k+j].c) )
								break;
						}
						// 2. if we matched the key, match whatever we have for the hint
						if (j == key.size()) {
							bMatchedThis = true;
							if (bHintInitialized) {
								unsigned int l = 0;
								for (; l < result.hint.size(); l++) {
									if ( towlower(result.hint[l]) != towlower(result.matches[i].str[k+j+l].c) )
										break;
								}
								result.hint = result.hint.substr(0, l); // second param is length
							} else {
								bHintInitialized = true;
								MatchStringToWString(result.matches[i].str.substr(k+j), result.hint);
							}
						}
					}
					bMatchedAll &= bMatchedThis;
				}
				/*timeHint.stopTimer();
				stringstream o;
				o << "hint compute took " << timeHint.getElapsedTime() << "s" << "\n";
				LOG(o.str());*/
			} else {
				for (unsigned int i = 0; i < haystack.size(); i++) {
					MatchOutput<T> mo;
					mo.data = haystack[i].data;
					WStringToMatchStringUnMatched(*(haystack[i].str), mo.str);
					result.matches.push_back(mo);
				}
			}
		}

		static int InnerMatch(matchstring& match, const wstring& key, const wstring& hole, int i, int j, int streak) {
			{
				wstringstream o;
				wstring ws;
				string s;
				MatchStringToWString(match, ws);
				o << "InnerMatch: (" << ws << "," << key << "," << hole << "," << i << "," << j << "," << streak << "\n";
				WStringToString(o.str(), s);
				LOG(s);
			}
			// if we ate the key before the whole, then score > 0
			if (key.size() == i) {
				// need to copy the rest of the hole to the match.
				for (unsigned int k = j; k < hole.size(); k++) {
					matchchar c;
					c.c = hole[k];
					c.matches = false;
					match.push_back(c);
				}
				return streak;
			}
			// if we ate the hole before the key, then score = 0
			if (hole.size() == j)
				return 0;

			// if this character matches, take the max of using the key here,
			// or using it later.

			matchchar c;
			c.c = hole[j];

			if (towlower(key[i]) == towlower(hole[j])) {

				// match them, eat both
				matchstring m1;
				int s1 = InnerMatch(m1, key, hole, i + 1, j + 1, streak + 1);
				// no match, move on
				matchstring m2;
				int s2 = InnerMatch(m2, key, hole, i, j + 1, 0);
				if (s1 >= s2) {
					// matching was better
					c.matches = true;
					match.push_back(c);
					match.append(m1);
					return s1;
				} else {
					// not matching was better
					c.matches = false;
					match.push_back(c);
					match.append(m2);
					return s2;
				}
			}
			// no match, move on
			c.matches = false;
			match.push_back(c);
			return InnerMatch(match, key, hole, i, j + 1, 0);
			
		}

		struct QueuedMatch {
			short parent;
			short startKey;
			short startHole;
		};
		int SimpleInnerMatch(matchstring& match, const wstring& key, const wstring& hole, int ui, int uj, int ustreak) {
			QueuedMatch toMatch[MAXSIZEX];
			toMatch[0].parent = -1;
			toMatch[0].startHole = 0;
			toMatch[0].startKey = 0;
			int leftToMatch= 1;

			int maxMatched = 0; // the best number of chars matched
			int nBestStreak = 0; // the streak length of the best match

			int idxCur = 0; // the current match index
			int idxBest = 0; // the best match index

			{
				stringstream o1;
				string skey;
				string shole;
				WStringToString(key, skey);
				WStringToString(hole, shole);
				o1 << "inner match { \"" << skey << "\", \"" << shole << "\"";
				LOG(o1.str());
			}

			// copy to the match
			WStringToMatchStringUnMatched(hole, match);
			while (leftToMatch > 0) {
				int curMatch = leftToMatch - 1;
				int i = toMatch[curMatch].startHole;
				int j = toMatch[curMatch].startKey;

				if (toMatch[curMatch].parent > -1) {
					// need to copy the matches from the parent to this match
					for (int k = 0; k < j; k++) {
						M(k, idxCur) = M(k, toMatch[curMatch].parent);
					}
				}
				int streak = 0;
				int nBestInnerStreak = 0;
				for (; i < hole.size(); i++) {
					if (j < key.size() && towlower(hole[i]) == towlower(key[j])) {
						M(j, idxCur) = i;

						toMatch[leftToMatch-1].parent = idxCur;
						toMatch[leftToMatch-1].startHole = i + 1;
						toMatch[leftToMatch-1].startKey = j;

						leftToMatch++;
						j++;
						streak++;
					} else {
						// end streak
						nBestInnerStreak = max(nBestInnerStreak, streak);
						streak = 0;
					}
					// invariants: len(matched) == j
				}
				// be sure to check the streak at the end!
				nBestInnerStreak = max(nBestInnerStreak, streak);
				if (j > maxMatched || (j == maxMatched && nBestInnerStreak > nBestStreak)) {
					maxMatched = j;
					idxBest = idxCur;
					nBestStreak = nBestInnerStreak;
				}
				leftToMatch--;
				idxCur++;

				if (maxMatched != key.size()) {
					leftToMatch = curMatch;
				}
			}
			
			if (maxMatched != key.size())
				return 0;

			// copy matches to match string
			for (int i = 0; i < key.size(); i++) {
				match[M(i,idxBest)].matches = true;
			}

			return nBestStreak;
		}
		static const int MAXSIZEX = 1024;
		static const int MAXSIZEY = 128;
	private:
		unsigned short& M(int i, int j) {
			return m_mat[MAXSIZEY*j + i];
		}

		unsigned short m_mat[MAXSIZEX*MAXSIZEY];
	};

}

